In some packet-based communications systems, a packet switch stores fixed-sized portions of data packets, which are often referred to as cells, at input ports of the packet switch. Further, the packet switch selects cells at the input ports and individually routes the selected cells to output ports of the packet switch. At the output ports, the packet switch identifies cells belonging to the same data packet, assembles the identified cells to reconstruct the data packet, and outputs the reconstructed data packet from the packet switch. In this type of packet switch, the order in which cells are routed from the input ports to the output ports of the packet switch impacts throughput of the packet switch.
One technique for selecting cells to route from input ports to output ports of a packet switch employs an oldest cells first (OCF) algorithm. In this technique, each input port includes virtual output queues, each of which represents an output port of the packet switch. The input port receives cells of a data packet, identifies an output port of the packet switch based on a header of the data packet, and maps the cells to the virtual output queue representing the identified output port. Further, the input port maintains a time stamp for each cell indicating how long the cell as been waiting in the virtual output queue. In turn, an arbiter in the packet switch selects cells that may be simultaneously routed from the input ports to the output ports of the packet switch, based on the time stamps of the cells and the ability of each output port to accept a cell. In this selection process, the arbiter gives preference to the oldest cells in the input ports. Although this technique has been successfully employed to route data packets through a packet switch, the size and complexity of logic for employing this technique in a packet switch grows exponentially as the number of input ports and output ports increases. Moreover, the speed of the logic for employing this technique decreases as the size and complexity of the logic increases, which reduces performance and throughput of the packet switch.
Throughput and performance of a packet switch employing this technique may also be adversely affected by multicast data packets. In particular, the packet switch may individually route a cell of a multicast data packet to each destination output port identified by the multicast data packet. Accordingly, the number of times the packet switch individually routes a cell of a multicast data packet from an input port of the packet switch to a destination output port of packet switch may be equal to the number of destination output ports identified by the multicast data packet. As a result, throughput of the packet switch is reduced when the packet switch routes the multicast data packet through the packet switch. Further, because the packet switch may route cells of other data packets from the input port to output ports of the packet switch between individually routing a cell of the multicast data packet to destination ports, the multicast data packet may experience increased latency in the packet switch. As a result, the latency of the multicast data packet is substantially higher than latencies of other data packets in the packet switch, which adversely affects performance of the packet switch.
In light of the above, a need exists for an improved system and method of routing data packets through a packet switch. A further need exists for increasing performance and throughput of a packet switch capable of routing multicast data packets.